from fractions import Fraction
import operator

__all__ = ["reduction"]



def inner_product(f, g):
    return sum(map(operator.mul, f, g))


def square(f):
    return sum(x ** 2 for x in f)


class LLL:

    __slots__ = ("F", "G", "L", "M", "n", "poly")

    def __init__(self, poly, mod):
        self.poly = poly
        self.n = poly.deg
        self.F = []
        for i in range(self.n):
            self.F.append([0] * i + [mod] + [0] * (self.n - i - 1))
        self.gram_schmidt()

    def add_vector(self):
        self.n += 1
        for l in self.F:
            l.append(0)
        for l in self.G:
            l.append(0)
        self.F.append([0] * (self.n - self.poly.deg - 1) + self.poly.coeff)
        self.orthogonal_row(self.n - 1)

    def reduction(self):
        L, n = self.L, self.n
        k = 1
        while k < n:
            self.row_reduction(k, k - 1)
            if L[k] ** 2 <= 2 * L[k - 1] * L[k + 1]:
                for i in range(k - 2, -1, -1):
                    self.row_reduction(k, i)
                k += 1
            else:
                self.swap_vector(k)
                k = max(1, k - 1)

    @property
    def short_vector(self):
        return self.F[0]

    def orthogonal_row(self, row):
        F, G, L, M, n = self.F, self.G, self.L, self.M, self.n
        G.append([L[row] * x for x in F[row]])
        M.append([])
        for i in range(row):
            M[row].append(inner_product(F[row], G[i]))
            m = Fraction(L[row] * M[row][i], L[i] * L[i + 1])
            for j in range(n):
                G[row][j] -= m * G[i][j]
        for i in range(n):
            G[row][i] = G[row][i].numerator
        L.append(square(G[row]) // L[row])

    def gram_schmidt(self):
        self.G = []
        self.L = [1]
        self.M = []
        for i in range(self.n):
            self.orthogonal_row(i)

    def row_reduction(self, k, i):
        F, M, n = self.F, self.M, self.n
        num = M[k][i]
        denom = self.L[i + 1]
        c = (num + (denom >> 1)) // denom
        if c:
            for j in range(n):
                F[k][j] -= c * F[i][j]
            for j in range(i):
                M[k][j] -= c * M[i][j]
            M[k][i] -= c * denom

    def swap_vector(self, k):
        F, G, L, M, n = self.F, self.G, self.L, self.M, self.n
        m = M[k][k - 1]
        for i in range(n):
            G[k - 1][i], G[k][i] = (
                    (L[k - 1] * G[k][i] + m * G[k - 1][i]) // L[k],
                    (L[k + 1] * G[k - 1][i] - m * G[k][i]) // L[k])
        for i in range(k + 1, n):
            M[i][k - 1], M[i][k] = (
                    (L[k - 1] * M[i][k] + m * M[i][k - 1]) // L[k],
                    (L[k + 1] * M[i][k - 1] - m * M[i][k]) // L[k])
        L[k] = (L[k - 1] * L[k + 1] + m ** 2) // L[k]
        F[k - 1], F[k] = F[k], F[k - 1]
        M[k - 1], M[k] = M[k], M[k - 1]
        M[k].append(M[k - 1].pop())
